#include "headfiles.h"

using namespace std;

NODE * copyLinkList(NODE *head) {
	if (head == NULL) {
		return NULL;
	}

	NODE *new_head = NULL;
	NODE *pre_node;
	NODE *n = head;
	while (n) {
		NODE *new_node = (NODE *)malloc(sizeof(NODE));
		memset(new_node, 0, sizeof(NODE));
		new_node->val = n->val;
		if (new_head == NULL) {
			new_head = pre_node = new_node;
		}
		else {
			pre_node->next = new_node;
			pre_node = new_node;
		}

		n = n->next;
	}

	return new_head;
}

// returned link list is a new one
NODE * addLinkLists(NODE *head1, NODE *head2) {
	if (head1 == NULL) {
		return copyLinkList(head2);
	}

	if (head2 == NULL) {
		return copyLinkList(head1);
	}

	NODE *new_head = NULL;
	NODE *pre_node;
	NODE *n1 = head1;
	NODE *n2 = head2;
	unsigned int carry = 0;
	unsigned sum;

	while (n1 != NULL && n2 != NULL) {
		sum = n1->val + n2->val + carry;
		carry = 0;
		if (sum >= 10) {
			carry = 1;
			sum -= 10;
		}

		NODE *new_node = (NODE *)malloc(sizeof(NODE));
		memset(new_node, 0, sizeof(NODE));
		new_node->val = sum;
		if (new_head == NULL) {
			new_head = pre_node = new_node;
		}
		else {
			pre_node->next = new_node;
			pre_node = new_node;
		}
		
		n1 = n1->next;
		n2 = n2->next;
	}

	while (n1 != NULL) {
		sum = n1->val + carry;
		carry = 0;
		if (sum >= 10) {
			sum -= 10;
			carry = 1;
		}

		NODE *new_node = (NODE *)malloc(sizeof(NODE));
		memset(new_node, 0, sizeof(NODE));
		new_node->val = sum;
		pre_node->next = new_node;
		pre_node = new_node;
		n1 = n1->next;
	}

	while (n2 != NULL) {
		sum = n2->val + carry;
		carry = 0;
		if (sum >= 10) {
			sum -= 10;
			carry = 1;
		}

		NODE *new_node = (NODE *)malloc(sizeof(NODE));
		memset(new_node, 0, sizeof(NODE));
		new_node->val = sum;
		pre_node->next = new_node;
		pre_node = new_node;
		n2 = n2->next;
	}

	if (carry) {
		NODE *new_node = (NODE *)malloc(sizeof(NODE));
		memset(new_node, 0, sizeof(NODE));
		new_node->val = 1;
		pre_node->next = new_node;
	}

	return new_head;
}
	

